package bintree.leetcode;

import java.util.LinkedList;

/**
 * @Author: yuisama
 * @Date: 2022/9/29 10:42
 * @Description:二叉树的序列化与反序列化
 */
public class Num297_Codec {
    // 前序遍历
    // Encodes a tree to a single string.
    private String SEP = ",";
    private String NULL = "#";
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) {
            return sb.toString();
        }
        traverse(root,sb);
        return sb.toString();
    }
    private void traverse(TreeNode root, StringBuilder sb) {
        //  base case
        if (root == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        traverse(root.left,sb);
        traverse(root.right,sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> nodesValue = new LinkedList<>();
        // 将字符串转为节点值列表
        for (String s : data.split(SEP)) {
            nodesValue.add(s);
        }
        TreeNode root = deserializeInternal(nodesValue);
        return root;
    }
    private TreeNode deserializeInternal(LinkedList<String> nodesValue) {
        // base case
        if (nodesValue.isEmpty()) {
            return null;
        }
        // 每次取根节点
        String s = nodesValue.removeFirst();
        if (s.equals(NULL) || s.isEmpty()) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(s));
        // 继续构造子树
        root.left = deserializeInternal(nodesValue);
        root.right = deserializeInternal(nodesValue);
        return root;
    }
}
